package com.sheng.leetcode.year2022.month05.day10;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author liusheng
 * @date 2022/05/10
 *
 * 913. 猫和老鼠
 *
 * 两位玩家分别扮演猫和老鼠，在一张 无向 图上进行游戏，两人轮流行动。
 * 图的形式是：graph[a] 是一个列表，由满足 ab 是图中的一条边的所有节点 b 组成。
 * 老鼠从节点 1 开始，第一个出发；猫从节点 2 开始，第二个出发。在节点 0 处有一个洞。
 * 在每个玩家的行动中，他们 必须 沿着图中与所在当前位置连通的一条边移动。
 * 例如，如果老鼠在节点 1 ，那么它必须移动到 graph[1] 中的任一节点。
 * 此外，猫无法移动到洞中（节点 0）。
 * 然后，游戏在出现以下三种情形之一时结束：
 * 如果猫和老鼠出现在同一个节点，猫获胜。
 * 如果老鼠到达洞中，老鼠获胜。
 * 如果某一位置重复出现（即，玩家的位置和移动顺序都与上一次行动相同），游戏平局。
 * 给你一张图 graph ，并假设两位玩家都都以最佳状态参与游戏：
 * 如果老鼠获胜，则返回 1；
 * 如果猫获胜，则返回 2；
 * 如果平局，则返回 0 。
 *
 * 示例 1：
 *
 * 输入：graph = [[2,5],[3],[0,4,5],[1,4,5],[2,3],[0,2,3]]
 * 输出：0
 * 示例 2：
 *
 * 输入：graph = [[1,3],[0],[3],[0,2]]
 * 输出：1
 *
 * 提示：
 *
 * 3 <= graph.length <= 50
 * 1 <= graph[i].length < graph.length
 * 0 <= graph[i][j] < graph.length
 * graph[i][j] != i
 * graph[i] 互不相同
 * 猫和老鼠在游戏中总是移动
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/cat-and-mouse
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0913 {

    @Test
    public void test01(){
        int[][] graph = {{2,5},{3},{0,4,5},{1,4,5},{2,3},{0,2,3}};
        System.out.println(new Solution().catMouseGame(graph));
    }

}
//class Solution {
//    public int catMouseGame(int[][] graph) {
//        return 0;
//    }
//}

//动态规划
//数据范围只有 50，使得本题的难度大大降低。
//定义 f[k][i][j] 为当前进行了 k 步，老鼠所在位置为 i，猫所在的位置为 j 时，
//最终的获胜情况（0 为平局，1 和 2 分别代表老鼠和猫获胜），
//起始我们让所有的 f[i][j][k] = -1（为无效值），最终答案为 f[0][1][2]。
//不失一般性的考虑 f[i][j][k] 该如何转移，根据题意，将当前所在位置 i 和 j 结合「游戏结束，判定游戏」的规则来分情况讨论：
//
//若 i = 0，说明老鼠位于洞中，老鼠获胜，此时有 f[k][i][j] = 1；
//若 i = j，说明两者为与同一位置，猫获胜，此时有 f[k][i][j] = 2；
//考虑如何定义平局，即 f[k][i][j] = 0 的情况？
//我们最多有 n 个位置，因此 (i, j) 位置对组合数最多为 n^2种，
//然后 k 其实代表的是老鼠先手还是猫先手，共有 2 种可能，因此状态数量数据有明确上界为 2 * n^2。
//所以我们可以设定 k 的上界为 2 * n^2（抽屉原理，走超过 2 * n^2步，必然会有相同的局面出现过至少两次），
//但是这样的计算量为 2 * 50^2 * 50 * 50 = 1.25 * 10^7，有 TLE 风险，转移过程增加剪枝，可以过。
//而更小的 k 值需要证明：在最优策略中，相同局面（状态）成环的最大长度的最小值为 k。
//题目规定轮流移动，且只能按照 graph 中存在的边进行移动。
//如果当前 k 为偶数（该回合老鼠移动），此时所能转移所有点为 f[k + 1][ne][j]，其中 ne 为 i 所能到达的点。
//由于采用的是最优移动策略，因此 f[k][i][j] 会优先往 f[k + 1][ne][j] = 1 的点移动（自身获胜），
//否则往 f[k + 1][ne][j] = 0 的点移动（平局），再否则才是往 f[k + 1][ne][j] = 2 的点移动（对方获胜）；
//同理，如果当前 k 为奇数（该回合猫移动），此时所能转移所有点为 f[k + 1][i][ne]，
//其中 ne 为 j 所能到达的点。由于采用的是最优移动策略，
//因此 f[k][i][j] 会优先往 f[k + 1][i][ne] = 2 的点移动（自身获胜），
//否则往 f[k + 1][i][ne] = 0 的点移动（平局），再否则才是往 f[k + 1][i][ne] = 1 的点移动（对方获胜）。
//使用该转移优先级进行递推即可，为了方便我们使用「记忆化搜索」的方式来实现动态规划。
//注意，该优先级转移其实存在「贪心」决策，但证明这样的决策会使得「最坏情况最好」是相对容易的，而证明存在更小的 k 值才是本题难点。
//一些细节：由于本身就要对动规数组进行无效值的初始化，
//为避免每个样例都 new 大数组，我们使用 static 来修饰大数组，可以有效减少一点时间（不使用 static 的话，N 只能取到 51）。
//
//class Solution {
//    static int N = 55;
//    static int[][][] f = new int[2 * N * N][N][N];
//    int[][] g;
//    int n;
//    public int catMouseGame(int[][] graph) {
//        g = graph;
//        n = g.length;
//        for (int k = 0; k < 2 * n * n; k++) {
//            for (int i = 0; i < n; i++) {
//                for (int j = 0; j < n; j++) {
//                    f[k][i][j] = -1;
//                }
//            }
//        }
//        return dfs(0, 1, 2);
//    }
//    // 0:draw / 1:mouse / 2:cat
//    int dfs(int k, int a, int b) {
//        int ans = f[k][a][b];
//        if (a == 0) ans = 1;
//        else if (a == b) ans = 2;
//        else if (k >= 2 * n * n) ans = 0;
//        else if (ans == -1) {
//            if (k % 2 == 0) { // mouse
//                boolean win = false, draw = false;
//                for (int ne : g[a]) {
//                    int t = dfs(k + 1, ne, b);
//                    if (t == 1) win = true;
//                    else if (t == 0) draw = true;
//                    if (win) break;
//                }
//                if (win) ans = 1;
//                else if (draw) ans = 0;
//                else ans = 2;
//            } else { // cat
//                boolean win = false, draw = false;
//                for (int ne : g[b]) {
//                    if (ne == 0) continue;
//                    int t = dfs(k + 1, a, ne);
//                    if (t == 2) win = true;
//                    else if (t == 0) draw = true;
//                    if (win) break;
//                }
//                if (win) ans = 2;
//                else if (draw) ans = 0;
//                else ans = 1;
//            }
//        }
//        f[k][a][b] = ans;
//        return ans;
//    }
//}
//
//作者：AC_OIer
//链接：https://leetcode.cn/problems/cat-and-mouse/solution/gong-shui-san-xie-dong-tai-gui-hua-yun-y-0bx1/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

//方法、记忆化搜索
//今天这道题我们分情况来讨论即可。
//老鼠行动的结果从好到坏依次是：老鼠赢 > 平局 > 猫赢。
//猫行动的结果从好到坏依次是：猫赢 > 平局 > 老鼠赢。
//所以，我们的代码也可以从这两个大的维度来组织代码，然后，再分别对应三种小情况。
//另外，因为无向图可能存在环，猫可能一直都抓不到老鼠，老鼠也一直走不到洞里去，
//这种情况就是平局，我们不能让它们无限在里面玩，所以，最多 2n 次行动之后，如果无法确定输赢就是平局了。
//为什么是 2n 次？因为 2n 次可以确保肯定有一个节点猫和老鼠走了两次，
//按照最优策略，它们都走回了原来走过的点，说明怎么走都胜不了，只能平局了。
//最后，按照 DFS 来遍历的话，存在相同的状态多次计算，所以，我们还要加上记忆化的逻辑，也就是记忆化搜索。
//请看代码，加了详细注释，相信你一定可以看明白：
//
class Solution {

    /**
     * 平局
     */
    private static final int DRAW = 0;
    /**
     * 老鼠赢
     */
    private static final int MOUSE_WIN = 1;
    /**
     * 猫赢
     */
    private static final int CAT_WIN = 2;

    public int catMouseGame(int[][] graph) {
        int n = graph.length;
        int[][][] memo = new int[n][n][2 * n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                Arrays.fill(memo[i][j], -1);
            }
        }
        return dfs(graph, n, memo, 2, 1, 0);
    }

    private int dfs(int[][] graph, int n, int[][][] memo, int catPos, int mousePos, int turns) {
        // 超过节点数两倍，可以确定为平局
        if (turns >= 2 * n) {
            return 0;
        }

        // 缓存中有，直接返回
        if (memo[catPos][mousePos][turns] != -1) {
            return memo[catPos][mousePos][turns];
        }

        // 老鼠赢
        if (mousePos == 0) {
            return memo[catPos][mousePos][turns] = MOUSE_WIN;
        }

        // 猫赢
        if (catPos == mousePos) {
            return memo[catPos][mousePos][turns] = CAT_WIN;
        }

        // turns 为偶数是轮到老鼠走，为奇数是轮到猫走
        if (turns % 2 == 0) {
            // 老鼠最坏情况是猫赢
            int ans = CAT_WIN;
            // 尝试走到下一个节点
            for (int nextPos : graph[mousePos]) {
                int nextAns = dfs(graph, n, memo, catPos, nextPos, turns + 1);
                // 如果老鼠可以赢，直接返回
                if (nextAns == MOUSE_WIN) {
                    return memo[catPos][mousePos][turns] = MOUSE_WIN;
                }
                // 有平局，先记录为平局，后面如果有老鼠可以赢的场景，通过上述语句可以返回
                if (nextAns == DRAW) {
                    ans = DRAW;
                }
            }
            // 返回老鼠走的结果
            return memo[catPos][mousePos][turns] = ans;
        } else {
            // 猫最坏情况是老鼠赢
            int ans = MOUSE_WIN;
            for (int nextPos : graph[catPos]) {
                // 注意猫不能走到0号节点
                if (nextPos != 0) {
                    // 尝试进入下一个节点
                    int nextAns = dfs(graph, n, memo, nextPos, mousePos, turns + 1);
                    // 如果猫可以赢，直接返回
                    if (nextAns == CAT_WIN) {
                        return memo[catPos][mousePos][turns] = CAT_WIN;
                    }
                    // 有平局，先记录为平局，后面如果有猫可以赢的场景，通过上述语句可以返回
                    if (nextAns == DRAW) {
                        ans = DRAW;
                    }
                }
            }
            // 返回猫走的结果
            return memo[catPos][mousePos][turns] = ans;
        }
    }
}
//
//作者：tong-zhu
//链接：https://leetcode.cn/problems/cat-and-mouse/solution/tong-ge-lai-shua-ti-la-dfs-ji-yi-hua-sou-ceb9/
//来源：力扣（LeetCode）
//著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
